package com.coder.algorithm.offer_2;

import java.util.Arrays;
import java.util.Locale;

/**
 * 二维数组中的查找
 *
 * @author yuhushuan
 * @date 2020/5/28 00:27
 */
public class _04_1_FindInPartiallySortedMatrix {
    public static void main(String[] args) {
        int[][] data = {
                {1, 2, 8, 9},
                {2, 4, 9, 12},
                {4, 7, 10, 13},
                {6, 8, 11, 15}
        };
        int number;
        boolean result;

        // 二维数组中包含查找的数字
        // 查找的数字是数组中的最大值和最小值；
        // 查找的数字介于数组中的最大值和最小值之间。
        System.out.println("查找的数字是数组中的最小值");
        print(data, 1);
        System.out.println("查找的数字是数组中的最大值");
        print(data, 15);
        System.out.println("查找的数字介于数组中的最大值和最小值之间");
        print(data, 10);

        // 二维数组中没有查找的数字
        // 查找的数字大于数组中的最大值；
        // 查找的数字小于数组中的最小值；
        // 查找的数字在数组的最大值和最小值之间但数组中没有这个数字。
        System.out.println("查找的数字大于数组中的最大值");
        print(data, 16);

        System.out.println("查找的数字小于数组中的最小值");
        print(data, 0);

        System.out.println("查找的数字在数组的最大值和最小值之间但数组中没有这个数字");
        print(data, 5);

        // 特殊输入测试（输入 null）。
        System.out.println("特殊输入测试（输入 null）");
        print(null, 5);
    }

    private static void print(int[][] matrix, int number) {
        printMatrix(matrix);
        if (matrix == null) {
            System.out.println(String.format(Locale.getDefault(), "查找数字：%d，结果为：%b"
                    , number, find(null, 0, 0, number)));
        } else {
            System.out.println(String.format(Locale.getDefault(), "查找数字：%d，结果为：%b"
                    , number, find(matrix, matrix.length, matrix[0].length, number)));
        }
        System.out.println();
    }

    private static void printMatrix(int[][] matrix) {
        System.out.println("二维数组：");
        if (matrix == null) {
            System.out.println("null");
            return;
        }
        for (int i = 0; i < matrix.length; ++i) {
            System.out.println(Arrays.toString(matrix[i]));
        }
    }

    /**
     * 题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上倒下递增的顺序。
     * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
     *
     * @return
     */
    private static boolean find(int[][] matrix, int rows, int columns, int number) {
        if (matrix == null || rows <= 0 || columns <= 0) {
            return false;
        }

        boolean found = false;

        int row = 0;
        int column = columns - 1;

        // 循环，条件 row 0,1,2,3; column = 3,2,1,0; found = true
        while (row < rows && column >= 0) {
            if (number == matrix[row][column]) {
                found = true;
                break;
            } else if (number < matrix[row][column]) {// 在目标左侧，排除当前列
                column--;
            } else if (number > matrix[row][column]) {// 在目标下册，排除当前行
                row++;
            }
        }
        return found;

    }
}
